package graph_depth_first_traversal;


import java.util.ArrayList;

/**
 * @author sijunqiang
 * @data 2021/6/12 17:19
 * @description: 图的深度优先遍历
 * 图的底层数据结构是 使用红黑树的进行存储节点
 * <p>
 * 功能：
 * 1：构建图
 * 2：递归的方式 dfs
 * 3: 获取dfs的结果
 */
public class GraphBSF {

    // 定义一个私有属性 前序优先遍历的存储的结果
    private ArrayList<Integer> pre = new ArrayList<>();

    // 后续优先遍历存储的结果
    private ArrayList<Integer> post = new ArrayList<>();


    // 定义一个图类对象,用来标记传进来的图对象
    private Graph G;

    // 定义一个布尔数组,用来标记图的节点是否已经遍历过
    // 这个设计非常的巧妙, 巧妙的地方是把图中的每个顶点的值当作数组的下标_,索引对应的值如果为false的话
    // 那么 说明这个顶点没有被遍历过 如果为true的话说明该顶点被遍历过。
    private boolean[] visited;

    // 构造函数 就是将已经构建好的图进行深度优先遍历。
    public GraphBSF(Graph G) {
        this.G = G;
        visited = new boolean[G.V()];//开辟空间 大小和图的节点一致

        // 如果图中有多个联通变量 还使用dfs(0)这种方式进行遍历的话就会存在有的顶点不能遍历到
        // 添加下面这个for循环的 可以保证一个图中有多个联通变量都能遍历到
        for (int v = 0; v < G.V(); v++) {
            if (!visited[v]) {
                dfs(v);
            }
        }
    }

    // 开始图的深度优先遍历
    // 遍历的流程是:第一,先遍历这个顶点,如果这个顶点关联其他的顶点，然后再依次的根据这个顶点循环的遍历。
    private void dfs(int v) {
        visited[v] = true;// 将这个顶点标记为true。  true-代表这个顶点已经遍历。
        pre.add(v);
        // 遍历这个顶点 所相邻的顶点
        for (int w : G.adj(v)) {
            if (!visited[w]) {//如果这个顶点中,其中关联的顶点没有被标记过 那么就需要再次的以这个顶点为顶点遍历。
                dfs(w);
            }
        }
        post.add(v);
    }

    // 前序优先遍历的结果
    public Iterable pre() {
        return pre;
    }

    // 后续优先遍历的结果
    public Iterable post() {
        return post;
    }


    public static void main(String[] args) {
        Graph graph = new Graph("graph_depth_first_traversal.txt");
        System.out.println(graph);
        GraphBSF graphBSF = new GraphBSF(graph);
        System.out.println(graphBSF.pre());
        System.out.println(graphBSF.post());
    }
}
